package Algorithm;

import java.util.Stack;

/**
 * 用栈实现队列
 * 特点：删除队列头部元素的时候，需要移动整个1号栈的元素，开销很大。
 */
public class QueueTest {
    public static void main(String[] args) {
        appendTail(1);
        appendTail(2);
        appendTail(3);
        deleteHead();
        deleteHead();
        appendTail(4);
        deleteHead();
        appendTail(5);
        deleteHead();
        deleteHead();
        deleteHead();
    }

    //用两个栈实现队列
    private static Stack<Object> stack1 = new Stack<Object>();
    private static Stack<Object> stack2 = new Stack<Object>();

    //在队列的末尾插入元素
    public static void appendTail(Object object) {
        stack1.push(object);
        System.out.println("已经将元素：" + object + "加入队列中!");
    }

    //删除队列的头部元素
    public static void deleteHead() {
        //如果2号栈不为空，则弹出二号栈的栈顶元素
        if (!stack2.empty()) {
            stack2.pop();
        } else {
            if (stack1.isEmpty()) {
                throw new RuntimeException("队列为空！");
            }
            //如果1号栈不为空，2号栈还是空的，则将1号栈中的元素全部压入2号栈，此时2号栈的栈顶元素就是队列的头元素
            while (!stack1.empty()) {
                Object item = stack1.pop();
                stack2.push(item);
            }
            deleteHead();
        }

    }

}
